'''
@author: noako
'''

from math import hypot, pi
from collections import namedtuple
from FuzzyFloat import FuzzyFloat


Point = namedtuple('Point', ['x',  'y' ])
Line =  namedtuple('Line',  ['p1', 'p2'])
Ray =   namedtuple('Ray',   ['pi', 'p' ]) #pi = initial point

# pretty printing for points
Point.__repr__ = lambda self: "({}, {})".format(self.x, self.y)

zero = FuzzyFloat(0)
time_unit = FuzzyFloat(10)

def Determinant2(matrix):
    return matrix[0][0]*matrix[1][1] - matrix[1][0]*matrix[0][1]

def Determinant3(matrix):
    return (  matrix[0][0]*Determinant2([matrix[1][1:3], matrix[2][1:3]])
            - matrix[0][1]*Determinant2([[matrix[1][0],matrix[1][2]], [matrix[2][0],matrix[2][2]]])
            + matrix[0][2]*Determinant2([matrix[1][0:2], matrix[2][0:2]]))

def LineLineIntersection(l1, l2):
    d1 = Determinant2([[l1.p1.x, l1.p1.y], [l1.p2.x, l1.p2.y]])
    d2 = Determinant2([[l2.p1.x, l2.p1.y], [l2.p2.x, l2.p2.y]])
    dx = Determinant2([[d1, l1.p1.x - l1.p2.x], [d2, l2.p1.x - l2.p2.x]])
    dy = Determinant2([[d1, l1.p1.y - l1.p2.y], [d2, l2.p1.y - l2.p2.y]])
    d = Determinant2([[l1.p1.x - l1.p2.x, l1.p1.y - l1.p2.y], [l2.p1.x - l2.p2.x , l2.p1.y - l2.p2.y]])
    if d == zero: return None #parallel
    x = dx / d
    y = dy / d
    return Point(x,y)
    
def IsOnRay(r, p):
    if r.pi.x != r.p.x:
        return (p.x - r.pi.x > zero) == (r.p.x - r.pi.x > zero)
    else:
        return (p.y - r.pi.y > zero) == (r.p.y - r.pi.y > zero)

def RayRayIntersection(r1, r2):
    # find the supporting lines' intersection
    p = LineLineIntersection(Line._make(r1), Line._make(r2))
    if p == None: return None #parallel
    # make sure the intersection is on r and r2
    if IsOnRay(r1, p) and IsOnRay(r2, p):
        return p
    else:
        return None

def SupportingLine(edge, time = 0):
    if time == zero:
        return Line(edge.origin.point, edge.destination().point)
            
    x_diff = edge.destination().point.x - edge.origin.point.x
    y_diff = edge.destination().point.y - edge.origin.point.y
    edge_length = FuzzyFloat(hypot(x_diff, y_diff))
    assert(edge_length != zero) 
    x_dist = -edge.speed*time*y_diff/edge_length
    y_dist =  edge.speed*time*x_diff/edge_length
    
    #p1
    x1 = edge.origin.point.x + x_dist
    y1 = edge.origin.point.y + y_dist
    p1 = Point(x1, y1)
    #p2
    x2 = edge.destination().point.x + x_dist
    y2 = edge.destination().point.y + y_dist
    p2 = Point(x2, y2)
    
    return Line(p1, p2)

class ParallelEdgesError(Exception):
    def __init__(self, edge1, edge2):
        self.msg = "The following parallel edges were found in the input: {}, {}".format( 
                    edge1, edge2)

def Bisector(edge1, edge2, vertex = None, time = zero):
    l1 = SupportingLine(edge1, time + time_unit)
    l2 = SupportingLine(edge2, time + time_unit)
    point = LineLineIntersection(l1, l2)
    if point == None: # parallel edges not allowed in input
        raise ParallelEdgesError(edge1, edge2)
    if vertex != None:
        # The vertex is the initial point of the bisector ray
        initial_point = vertex.point
    else: #it's a line
        l1 = SupportingLine(edge1, time)
        l2 = SupportingLine(edge2, time)
        initial_point = LineLineIntersection(l1, l2)
    return Ray(initial_point, point)

def PointToLineDistance(point, line):
    segment_length = FuzzyFloat(hypot(line.p1.x - line.p2.x, line.p1.y - line.p2.y))
    assert(segment_length != zero)
    return (abs((line.p2.x - line.p1.x)*(line.p1.y - point.y)
              - (line.p2.y - line.p1.y)*(line.p1.x - point.x))
            /segment_length)

def ToTheRight(ray, point):
    # returns true iff the point is to the right of the ray
    p1 = ray.pi
    p2 = point
    p3 = ray.p
    return 0 < Determinant3([[p1.x, p2.x, p3.x],
                             [p1.y, p2.y, p3.y],
                             [1,    1,    1]])

def ToTheLeft(ray, point):
    # returns true iff the point is to the left of the ray 
    p1 = ray.pi
    p2 = point
    p3 = ray.p
    return 0 > Determinant3([[p1.x, p2.x, p3.x],
                             [p1.y, p2.y, p3.y],
                             [1,    1,    1]])

def AngleBetween(a1, a2, a3):
    # checks if the angle a2 is between a1 and a3
    # e.g. if we rotate a vector with angle a1 around the origin in counter-clockwise direction 
    # we will encounter a vector with angle a2 before one with angle a3
    # does not matter how the angles are represented (e.g. 0 <= a < 2pi or -pi <= a < pi or any similar option)
    # as long as all three angles use the same representation
      
    if a1 <= a3: return (a1 <= a2 and a2 <= a3)
    else:        return (a1 <= a2 or  a2 <= a3)

def IsOpposingEdge(edge, node):
    # verifies that the edge is actually opposing to the reflex vertex
    
    a_r = node.right_edge.angle()
    a_l = node.left_edge.angle()
    # rotate both angles by pi 
    a_r += (pi if a_r < 0 else -pi)
    a_l += (pi if a_l < 0 else -pi)
    
    return AngleBetween(a_r, edge.angle(), a_l)